package interviewQuestions;

import java.util.Stack;

class ListNode{ // 链表的节点
    ListNode next;
    int val;
    public ListNode(){

    }

    public ListNode(ListNode next, int val) {
        this.next = next;
        this.val = val;
    }
}

// 反转列表
public class ReverseList {
    static Stack<ListNode> stack = new Stack<>();
    ListNode node = new ListNode();

    public static ListNode revereList(ListNode head){
        ListNode pre = head;
        ListNode cur = null;
        while (pre != null){
            // 实例化一个临时节点 指向 pre的下一个节点
            ListNode temp = pre.next;
            // 将pre的下一个指向cur(cur事实上就是pre的上一个节点，形成了一个反正)
            pre.next = cur;
            cur = pre;// 往下走
            pre = temp;// 往下走
        }
        return cur;
    }

    // 递归实现
    public static ListNode revereList1(ListNode head){
        if(head == null || head.next == null){
            return head;
        }else{
            ListNode r = revereList1(head.next);
            head.next.next = head; // 逆转链表
            head.next = null; // 防止成环形引用
            return r;
        }
    }

    // 栈实现
    public static void reverseList2(ListNode head){

    }




    public static void main(String[] args) {
        ListNode l1 = new ListNode(null,1);
        ListNode l2 = new ListNode(l1,2);
        ListNode l3 = new ListNode(l2,3);
        ListNode l4 = new ListNode(l3,4);
        ListNode l5 = new ListNode(l4,5);
        ListNode result = revereList1(l5);
        while(result != null){
            System.out.println(result.val);
            result = result.next;
        }

    }
}
